package sort;

import java.util.Arrays;

public class InsertionSort {
    /*
    时间复杂度
    最坏情况（逆序数组）：O(n²)（每次插入需比较全部已排序元素）。
    最好情况（已排序数组）：O(n)（只需比较一次）。
    平均情况：O(n²)。
    空间复杂度 O(1)
     */
    public static void insertionSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int j = i-1;
            int key = arr[i];
            while(j>=0&&arr[j]>key){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1]=key;
        }
    }

    public static void main(String[] args) {
        int[] a = {39,4,564,345,667,3,45,6,67,8,34,5,1,41};
        insertionSort(a);
        System.out.println(Arrays.toString(a));
    }
}
